0334. 递增的三元子序列【中等】
1. 📝 题目描述
给你一个整数数组 nums,判断这个数组中是否存在长度为 3 的递增子序列。
如果存在这样的三元组下标 (i, j, k) 且满足 i < j < k,使得 nums[i] < nums[j] < nums[k],返回 true ;否则,返回 false。
示例 1:
txt
输入:nums = [1,2,3,4,5]
输出:true
解释:任何 i < j < k 的三元组都满足题意1
2
3
2
3
示例 2:
txt
输入:nums = [5,4,3,2,1]
输出:false
解释:不存在满足题意的三元组1
2
3
2
3
示例 3:
txt
输入:nums = [2,1,5,0,4,6]
输出:true
解释:其中一个满足题意的三元组是 (3, 4, 5),因为 nums[3] == 0 < nums[4] == 4 < nums[5] == 61
2
3
2
3
提示:
1 <= nums.length <= 5 * 10^5-2^31 <= nums[i] <= 2^31 - 1
进阶:你能实现时间复杂度为 O(n),空间复杂度为 O(1) 的解决方案吗?
2. 🎯 s.1 - 贪心
c
bool increasingTriplet(int* nums, int numsSize) {
int first = INT_MAX, second = INT_MAX;
for (int i = 0; i < numsSize; i++) {
if (nums[i] <= first) first = nums[i];
else if (nums[i] <= second) second = nums[i];
else return true;
}
return false;
}1
2
3
4
5
6
7
8
9
2
3
4
5
6
7
8
9
js
/**
* @param {number[]} nums
* @return {boolean}
*/
var increasingTriplet = function (nums) {
let first = Infinity,
second = Infinity
for (const num of nums) {
if (num <= first) first = num
else if (num <= second) second = num
else return true
}
return false
}1
2
3
4
5
6
7
8
9
10
11
12
13
14
2
3
4
5
6
7
8
9
10
11
12
13
14
py
class Solution:
def increasingTriplet(self, nums: List[int]) -> bool:
first = second = float('inf')
for num in nums:
if num <= first:
first = num
elif num <= second:
second = num
else:
return True
return False1
2
3
4
5
6
7
8
9
10
11
2
3
4
5
6
7
8
9
10
11
- 时间复杂度:
,其中 是数组长度 - 空间复杂度:
算法思路:
- 维护两个变量
first和second,分别表示最小值和次小值 - 若当前元素大于
second,则找到了递增的三元子序列